package com.lw.leetcode.stack.b;

/**
 * Created with IntelliJ IDEA.
 * stack
 * 334. 递增的三元子序列
 *
 * @author liw
 * @version 1.0
 * @date 2021/10/18 13:13
 */
public class IncreasingTriplet {

    public static void main(String[] args) {
        IncreasingTriplet test = new IncreasingTriplet();
//        int[] arr = {1,2,3,4,5};
//        int[] arr = {1,2,3};
//        int[] arr = {5,4,3,2,1};
//        int[] arr = {4,5,2,3,1,2};
        int[] arr = {1,2,1,2,1,2,1,2};
//        int[] arr = {1,5,0,4,1,3};

        boolean b = test.increasingTriplet(arr);
        System.out.println(b);
    }

    public boolean increasingTriplet(int[] nums) {

        int length = nums.length;
        if (length < 3) {
            return false;
        }
        int[] arr = new int[3];
        arr[0] = Integer.MAX_VALUE;
        arr[1] = Integer.MAX_VALUE;
        arr[2] = Integer.MAX_VALUE;
        int max = -1;
        int item = 0;
        for (int num : nums) {
            item = max;
            while (item >= 0 && arr[item] >= num) {
                item--;
            }
            if (item == max) {
                max++;
                if (item == 1) {
                    return true;
                }
            }
            arr[item + 1] = num;
        }
        return false;
    }
}
